#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/4 16:17
# @USER    : Shengji He
# @File    : ProductArrayExceptSelf.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        """
        Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal
        to the product of all the elements of nums except nums[i].

        :param nums: List[int]
        :return: List[int]

        Example:
            Input:  [1,2,3,4]

            Output: [24,12,8,6]

        Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array
        (including the whole array) fits in a 32 bit integer.

        Note: Please solve it without division and in O(n).

        Follow up:
        Could you solve it with constant space complexity? (The output array does not count as extra space
        for the purpose of space complexity analysis.)
        """
        ans = [1] * len(nums)
        r = 1
        for i in range(1, len(nums)):
            ans[i] = ans[i - 1] * nums[i - 1]
        for i in range(len(nums) - 1, -1, -1):
            ans[i] = ans[i] * r
            r *= nums[i]

        return ans


if __name__ == '__main__':
    S = Solution()
    nums = [1, 2, 3, 4]
    print(S.productExceptSelf(nums))
    print('done')
